This invention relates to string search methods and apparatus, and particularly those string search methods and apparatus as used in compression and encoding methods and apparatus.
There are many data compression and encoding methods and apparatus known today. Due to the everincreasing need to transmit and/or store greater and greater amounts of data, however, there is continued demand for increasingly improved data compression and encoding, both in terms of improved speed and reduced memory requirements, and above all in terms of greater compression efficiency. This demand can be seen by comparing Eastman et al., U.S. Pat. No. 4,464,650, with Welch, U.S. Pat. No. 4,558,302. From these two patents, and the references cited therein, it can be seen that work continues in the area of data compression and encoding.
The methods disclosed in the two patents above are described by some in the industry as Ziv-Lempel compression and Ziv-Lempel-Welch compression, respectively. Both of these methods are based on storage of recurring strings in tree form, requiring adding a new "leaf" node with the occurrence of a string not previously encountered. Another class of methods which may have certain advantages over either of the methods set forth above is described as "sliding window" data compression, wherein compression is achieved by comparing a certain string to be compressed to earlier portions of the string and reproducing the current string merely by referring to any similar earlier portions of the string found by the comparison. Since the earlier portions of the string need to be searched, however, to determine whether the subject string is repeated or not, efficient string searching becomes of greater importance.
This invention relates to improvements over the apparatus described above and to solutions to the problems raised or not solved thereby.